package xyf.p11.other.slidewindow;

import java.util.*;

/**
 * ClassName: P0438_FindAnagrams
 * Description:
 * Author: xyf
 * Date: 9/9/22 10:19 AM
 * Version: 1.0
 **/
public class P0438_FindAnagrams
{
    public List<Integer> findAnagrams(String s, String p)
    {
        HashMap<Character, Integer> sMap = new HashMap<>();

        HashMap<Character, Integer> pMap = new HashMap<>();

        for (int i = 0; i < p.length(); i++)
        {
            Integer cnt = pMap.getOrDefault(p.charAt(i), 0);
            pMap.put(p.charAt(i), cnt + 1);
        }

        int slow = 0;

        int fast = 0;

        List<Integer> res = new ArrayList<>();
        while (fast < s.length())
        {
            if (fast - slow == p.length())
            {
                if (check(sMap, pMap))
                {
                    res.add(slow);
                }

                Integer cnt1 = sMap.getOrDefault(s.charAt(slow), 0);
                sMap.put(s.charAt(slow), cnt1 - 1);
                slow++;
            }

            Integer cnt = sMap.getOrDefault(s.charAt(fast), 0);
            sMap.put(s.charAt(fast), cnt + 1);
            fast++;
        }

        if (fast - slow == p.length())
        {
            if (check(sMap, pMap))
            {
                res.add(slow);
            }
        }

        return res;
    }

    private boolean check(HashMap<Character, Integer> sMap, HashMap<Character, Integer> pMap)
    {
        for (Map.Entry<Character, Integer> entry : pMap.entrySet())
        {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            Integer cur = sMap.get(key);
            if (cur == null || !cur.equals(value))
            {
                return false;
            }
        }
        return true;
    }
}